public class BinarySearchTree {

    static  class TreeNdoe{
        public int val;
        public TreeNdoe left;
        public TreeNdoe right;
        public TreeNdoe(int val){
        this.val = val;
        }
    }


    public TreeNdoe root = null;

    /**
     * 查找二叉搜索树中指定val的值
     * @param val
     * @return
     */

    public TreeNdoe find(int val){
       TreeNdoe cur = root;
       while (cur != null){
           if(cur.val < val){
               cur = cur.right;
           }else if (cur.val == val){
               return cur;
           }else {
               cur = cur.left;
           }
       }
        return null;
    }

    /**
     * 插入一个数据
     * @param val
     */

    public void inset(int val){
        if(root == null){
            root = new TreeNdoe(val);
            return;
        }
        TreeNdoe cur = root ;
        TreeNdoe parent = null;
        while (cur != null){
            if (cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val){
                return;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        TreeNdoe node = new TreeNdoe(val);
        if (parent.val < val){
            parent.right = node ;
        }else {
            parent.left = node;
        }
    }

    public void inorder (TreeNdoe root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    /**
     * 删除值为val的节点
     * @param val
     */
    public void remove(int val ){
        TreeNdoe cur = root;
        TreeNdoe parent = null;
        while (cur != null){
            if(cur.val == val){
                removeNdoe(parent,cur);
                return;
            }else if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    private void removeNdoe(TreeNdoe parent, TreeNdoe cur) {
        if (cur.left == null){
           if (cur == root){
               root = cur.right;
           }else if (parent.left == cur){
               parent.left = cur.right;
           }else {
               parent.right = cur.right;
           }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.right;
            }else if (parent.left == cur){
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        }else {
            TreeNdoe target = cur.right;
            TreeNdoe targetParent = cur;
            while (target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left){
                targetParent.left = target.right;
            }else {
                targetParent.left = target.right;
            }


        }
    }

}
